package datastructure.graph.有向图;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/27 6:39 下午
 */
public class KosarajuSCC {
    private boolean[] marked;
    private int[] id;
    private int count;

    public KosarajuSCC(Digraph digraph) {
        marked=new boolean[digraph.V()];
        id=new int[digraph.V()];
        DepthFirstOrder order=new DepthFirstOrder(digraph.reverse());
        Iterable<Integer> reverseOrder = order.reversePost();
        for (Integer s : reverseOrder) {
            if (!marked[s]){
                dfs(digraph,s);
                count++;
            }
        }
    }

    private void dfs(Digraph digraph, Integer v) {
        marked[v]=true;
        id[v]=count;
        for (Integer w : digraph.adj(v)) {
            if (!marked[w]){
                dfs(digraph,w);
            }
        }
    }

    public boolean strongConnected(int v,int w){
        return id[v]==id[w];
    }

    public static void main(String[] args) {
        Digraph graph=new Digraph(13);
        graph.addEdge(0,1);
        graph.addEdge(0,5);
        graph.addEdge(2,0);
        graph.addEdge(2,3);
        graph.addEdge(3,2);
        graph.addEdge(3,5);
        graph.addEdge(4,3);
        graph.addEdge(5,4);
        graph.addEdge(6,4);
        graph.addEdge(6,0);
        graph.addEdge(6,9);
        graph.addEdge(7,6);
        graph.addEdge(7,8);
        graph.addEdge(8,7);
        graph.addEdge(9,10);
        graph.addEdge(9,11);
        graph.addEdge(10,12);
        graph.addEdge(11,12);
        graph.addEdge(12,9);
        KosarajuSCC scc=new KosarajuSCC(graph);
        System.out.println(scc.strongConnected(6,9));
        System.out.println(scc.strongConnected(12,9));
        System.out.println(scc.strongConnected(7,8));
        System.out.println(scc.strongConnected(2,3));
        System.out.println(scc.strongConnected(1,0));


        System.out.println(scc.count);
    }
}
